package oj.oj_692;

/**
 * 前K个高频单词
 */

import java.util.*;

public class Solution {
    static class Cmp implements Comparator<Map.Entry<String, Integer>> {
        @Override
        public int compare(Map.Entry<String, Integer> o1, Map.Entry<String, Integer> o2) {

            // i-2 < love-2 < coding-1 < leetcode-1
            String word1 = o1.getKey();
            int count1 = o1.getValue();

            String word2 = o2.getKey();
            int count2 = o2.getValue();

            if (count1 < count2) {
                // o1: coding-1
                // o2: i-2
                // o1 > o2
                return 1;
            } else if (count1 > count2) {
                // o1: i-2
                // o2: coding-1
                // o1 < o2
                return -1;
            }

            return word1.compareTo(word2);
        }
    }

    public List<String> topKFrequent(String[] words, int k) {
        Map<String, Integer> countMap = new TreeMap<>();
        for (String w : words) {
            int count = countMap.getOrDefault(w, 0);
            countMap.put(w, count + 1);
        }

        // 得到每个单词的出现次数

        // 先使用排序来完成
        // List
        // 元素  单词-次数   Entry<单词, 次数>
        // List<Entry<单词, 次数>> list
        // 要排序，意味元素是具备比较能力的，目前不具备
        // Comparator<Entry<单词, 次数>>
        // 默认情况下的排序：升序
        //  i-2 < love-2 < coding-1 < leetcode-1
        Set<Map.Entry<String, Integer>> entrySet = countMap.entrySet();
        // Set -> List
        List<Map.Entry<String, Integer>> list = new ArrayList<>(entrySet);
        // 对 List 进行排序
        Cmp comparator = new Cmp();
        Collections.sort(list, comparator);

        List<String> ans = new ArrayList<>();
        for (int i = 0; i < k; i++) {
            Map.Entry<String, Integer> entry = list.get(i);
            String word = entry.getKey();
            ans.add(word);
        }

        return ans;
    }
}

